package dynamicProgram;

import java.util.Arrays;

public class DynamicProgram {
    static int[] wp = {1,2,3,4};
    static int tj[] = {2,3,4,5};
    static int jz[] = {3,4,5,6};
    static int num = 8;
    public static void main(String[] args) {
        //定义背包容量


        //横向 num+1 容量 竖 物品个数
        int[][] a = new int[wp.length+1][num+1];
        for (int i = 0; i < a.length; i++) {
//            System.out.println(Arrays.toString(a[i]));
        }
        //容量累加
        for (int i = 1; i < num+1; i++) {
            caculate(1,i,a);
        }
//        caculate(1,5,a,0);
        for (int i = 0; i < a.length; i++) {
            System.out.println(Arrays.toString(a[i]));
        }
        System.out.println( a[4][8]);
        String s = String.valueOf(returnWpNo(8, a, 4, new StringBuilder()));
        System.out.println(s);
    }

    /**
     * 表格a【i】【j】表示的是容量为j的背包装入前i个物品的最大价值。
     * 拿a【1】【3】和a【2】【3】举例，这里的a【2】【3】意思并不是在a【1】【3】的基础上考虑第2件物品，而应该理解为再拿一个空背包考虑前两件物品的情况。
     * 因此，如果空间不足以放入第2件，那么a【2】【3】=a【1】【3】；如果空间足够放入第2件，那么将背包容量减去第2件的容量，得j=3-3=0，而i=2-1等于1，找到a【1】【0】=0，那么物品2价值加上a【1】【0】得到总价值4，将4与a【1】【3】比较，取较大值即为a【2】【3】的值。
     * 其他格子同理，如a【4】【8】，物品4价值6容量5，j=8-5=3，i=4-1=3，
     * 找到a【3】【3】值为4，6+4=10，10与a【3】【8】比较，10大，所以a【4】【8】=10。
     * 价值 只能为正
     * @param wpIndex 物品个数 从1 开始 0都是0 无需计算
     * @param rl 指定容量
     * @param a 动态规划数组
     */
    public static void caculate(int wpIndex,int rl,int[][] a){
        if(wpIndex  > wp.length ){
            return;
        }
        //物品本身能放
        if(rl>=tj[wpIndex-1]){
            //剩余容量 的wpIndex-1 处最佳的值 是多少
            int oldrl = rl- tj[wpIndex-1];
            int i = a[wpIndex - 1][oldrl];
            // 相加 得到值 和上一个值判断 大于则
            int i1 = jz[wpIndex - 1] + i;
            if(i1>a[wpIndex-1][rl]){
                a[wpIndex][rl] = i1;
            }else {
                a[wpIndex][rl] = a[wpIndex-1][rl];
            }
        }else {
            a[wpIndex][rl] = a[wpIndex-1][rl];
        }
        //物品选择 增加
        wpIndex++;
        caculate(wpIndex,rl,a);
    }

    /**
     * 给定容量 返回塞了 那几个物件
     * @param rl
     */
    public static StringBuilder returnWpNo(int rl,int[][] a,int wpIndex,StringBuilder no){
        if(wpIndex-1<0){
            return no.append("");
        }
        int item = a[wpIndex][rl];
        int item2 = a[wpIndex-1][rl];
        if(item2 != item){
            no .append( wp[wpIndex-1]);
            returnWpNo(rl-tj[wpIndex-1],a,wpIndex-1,no);
        }else {
            returnWpNo(rl,a,wpIndex-1,no);
        }
        return no;
    }
}

